\relax 
\providecommand\hyper@newdestlabel[2]{}
\providecommand*{\memsetcounter}[2]{}
\catcode`"\active
\providecommand\HyperFirstAtBeginDocument{\AtBeginDocument}
\HyperFirstAtBeginDocument{\ifx\hyper@anchor\@undefined
\global\let\oldcontentsline\contentsline
\gdef\contentsline#1#2#3#4{\oldcontentsline{#1}{#2}{#3}}
\global\let\oldnewlabel\newlabel
\gdef\newlabel#1#2{\newlabelxx{#1}#2}
\gdef\newlabelxx#1#2#3#4#5#6{\oldnewlabel{#1}{{#2}{#3}}}
\AtEndDocument{\ifx\hyper@anchor\@undefined
\let\contentsline\oldcontentsline
\let\newlabel\oldnewlabel
\fi}
\fi}
\global\let\hyper@last\relax 
\gdef\HyperFirstAtBeginDocument#1{#1}
\providecommand\HyField@AuxAddToFields[1]{}
\providecommand\HyField@AuxAddToCoFields[2]{}
\@input{titlepage.aux}
\@input{titlepage_en.aux}
\citation{1970codd}
\citation{2008xml,2006xml}
\citation{1984kupervardi,1987kunii}
\citation{2008angles}
\citation{2010foundsemweb}
\citation{2000GO}
\citation{1995databases}
\@writefile{lof}{\addvspace {10pt}}
\@writefile{lot}{\addvspace {10pt}}
\@writefile{toc}{\contentsline {chapter}{\chapternumberline {1}Introduction}{1}{chapter.1}}
\@writefile{loa}{\addvspace {10\p@ }}
\newlabel{ch:intro}{{\M@TitleReference {1}{Introduction}}{1}{Introduction}{chapter.1}{}}
\citation{1971codd,1971codd2}
\citation{beeri1978}
\citation{1974codd}
\citation{2002arenas}
\providecommand*\caption@xref[2]{\@setref\relax\@undefined{#1}}
\newlabel{fig:rel_articles}{{\M@TitleReference {1.1a}{Data stored in a table.\relax }}{2}{Data stored in a table.\relax }{figure.caption.5}{}}
\newlabel{sub@fig:rel_articles}{{\M@TitleReference {a}{Data stored in a table.\relax }}{2}{Data stored in a table.\relax }{figure.caption.5}{}}
\newlabel{fig:xml_articles}{{\M@TitleReference {1.1b}{Data stored in a tree.\relax }}{2}{Data stored in a tree.\relax }{figure.caption.5}{}}
\newlabel{sub@fig:xml_articles}{{\M@TitleReference {b}{Data stored in a tree.\relax }}{2}{Data stored in a tree.\relax }{figure.caption.5}{}}
\newlabel{fig:gdb_articles}{{\M@TitleReference {1.1c}{Data stored in a graph.\relax }}{2}{Data stored in a graph.\relax }{figure.caption.5}{}}
\newlabel{sub@fig:gdb_articles}{{\M@TitleReference {c}{Data stored in a graph.\relax }}{2}{Data stored in a graph.\relax }{figure.caption.5}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {1.1}{\ignorespaces Information on conference articles stored in different data models.\relax }}{2}{figure.caption.5}}
\newlabel{fig:articles}{{\M@TitleReference {1.1}{Information on conference articles stored in different data models.\relax }}{2}{Information on conference articles stored in different data models.\relax }{figure.caption.5}{}}
\citation{1970codd}
\citation{2006xml}
\citation{2001xsd}
\citation{2004arenas}
\newlabel{fig:rel_articles_rep}{{\M@TitleReference {1.2a}{Data stored in tables.\relax }}{3}{Data stored in tables.\relax }{figure.caption.6}{}}
\newlabel{sub@fig:rel_articles_rep}{{\M@TitleReference {a}{Data stored in tables.\relax }}{3}{Data stored in tables.\relax }{figure.caption.6}{}}
\newlabel{fig:xml_articles_rep}{{\M@TitleReference {1.2b}{Data stored in a tree.\relax }}{3}{Data stored in a tree.\relax }{figure.caption.6}{}}
\newlabel{sub@fig:xml_articles_rep}{{\M@TitleReference {b}{Data stored in a tree.\relax }}{3}{Data stored in a tree.\relax }{figure.caption.6}{}}
\newlabel{fig:gdb_articles_rep}{{\M@TitleReference {1.2c}{Data stored in a graph.\relax }}{3}{Data stored in a graph.\relax }{figure.caption.6}{}}
\newlabel{sub@fig:gdb_articles_rep}{{\M@TitleReference {c}{Data stored in a graph.\relax }}{3}{Data stored in a graph.\relax }{figure.caption.6}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {1.2}{\ignorespaces Information on conference articles stored in different data models.\relax }}{3}{figure.caption.6}}
\newlabel{fig:articles_rep}{{\M@TitleReference {1.2}{Information on conference articles stored in different data models.\relax }}{3}{Information on conference articles stored in different data models.\relax }{figure.caption.6}{}}
\citation{2006calvanese}
\citation{2009baader}
\citation{2008calvanese}
\citation{2012rdbmapping}
\citation{2012Sequeda}
\citation{2012rdbmapping}
\citation{2012Sequeda}
\citation{2008calvanese}
\citation{1970codd}
\citation{1971codd,1971codd2}
\citation{1974codd}
\citation{1977fagin,1979fagin}
\citation{1981fagin}
\citation{2002darwen}
\citation{2012darwen}
\citation{2008xml,2006xml}
\citation{2001embley}
\citation{2002arenas,2004arenas,2006arenas}
\citation{2003arenas}
\citation{2002lee}
\@writefile{toc}{\contentsline {paragraph}{Contributions.}{5}{section*.7}}
\@writefile{toc}{\contentsline {paragraph}{State of the Art.}{5}{section*.8}}
\citation{1984kupervardi,1987kunii}
\citation{2013baeza,2013baeza2,2013libkin}
\citation{2001semanticweb,2006semanticweb}
\citation{2004rdf}
\citation{2004rdfs}
\citation{2004owl,2012owl}
\citation{2012owl}
\citation{2012owl2semantics}
\citation{2012owl2prof}
\citation{2006calvanese}
\citation{2009artale}
\citation{2003baader}
\citation{2011lenzerini}
\citation{2013calvanese2}
\citation{2001calvanese,2008calvanese}
\citation{2007calvanese}
\citation{2001calvanese}
\citation{2008calvanese}
\citation{2009romero}
\citation{2004arenas}
\@writefile{toc}{\contentsline {paragraph}{Organization.}{6}{section*.9}}
\citation{1992mannila,1995databases,2006arenas2}
\citation{1970codd}
\citation{2006arenas2}
\@writefile{lof}{\addvspace {10pt}}
\@writefile{lot}{\addvspace {10pt}}
\@writefile{toc}{\contentsline {chapter}{\chapternumberline {2}Existing Normal Forms For Relational Data}{7}{chapter.2}}
\@writefile{loa}{\addvspace {10\p@ }}
\newlabel{ch:relational}{{\M@TitleReference {2}{Existing Normal Forms For Relational Data}}{7}{Existing Normal Forms For Relational Data}{chapter.2}{}}
\@writefile{toc}{\contentsline {section}{\numberline {2.1}Preliminaries}{7}{section.2.1}}
\newlabel{sec:relPre}{{\M@TitleReference {2.1}{Preliminaries}}{7}{Preliminaries}{section.2.1}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {2.1}{\ignorespaces Relation $course$\relax }}{8}{figure.caption.10}}
\newlabel{fig:relCourse}{{\M@TitleReference {2.1}{Relation $course$\relax }}{8}{Relation $course$\relax }{figure.caption.10}{}}
\@writefile{toc}{\contentsline {section}{\numberline {2.2}Data Dependencies}{8}{section.2.2}}
\newlabel{sec:relDep}{{\M@TitleReference {2.2}{Data Dependencies}}{8}{Data Dependencies}{section.2.2}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2.1}Functional Dependencies}{8}{subsection.2.2.1}}
\newlabel{ssec:rel_fd}{{\M@TitleReference {2.2.1}{Functional Dependencies}}{8}{Functional Dependencies}{subsection.2.2.1}{}}
\citation{1979beeribernstein,1979bernstein}
\citation{1992mannila}
\citation{1992mannila}
\citation{1974armstrong}
\newlabel{eqn:fd_c1}{{2.1}{9}{Functional Dependencies}{equation.2.2.1}{}}
\newlabel{eqn:fd_c2}{{2.2}{9}{Functional Dependencies}{equation.2.2.2}{}}
\newlabel{eqn:fd_c3}{{2.3}{9}{Functional Dependencies}{equation.2.2.3}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.1.1}Implication of FDs}{9}{subsubsection.2.2.1.1}}
\newlabel{sssec:fd_impl}{{\M@TitleReference {2.2.1.1}{Implication of FDs}}{9}{Implication of FDs}{subsubsection.2.2.1.1}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.2.1.2}Axiomatization for FDs}{9}{subsubsection.2.2.1.2}}
\newlabel{sssec:fd_axiom}{{\M@TitleReference {2.2.1.2}{Axiomatization for FDs}}{9}{Axiomatization for FDs}{subsubsection.2.2.1.2}{}}
\citation{1995databases}
\citation{1992mannila}
\citation{1992mannila}
\citation{1971codd,1971codd2}
\@writefile{loa}{\contentsline {algocf}{\numberline {2.1}{\ignorespaces Linear time algorithm to compute the closure $X^+$ of a set of attributes $X$ (from \cite  {1992mannila})\relax }}{10}{algocf.2.1}}
\newlabel{alg:beeri}{{\M@TitleReference {2.1}{Implication of FDs}}{10}{Implication of FDs}{algocf.2.1}{}}
\@writefile{toc}{\contentsline {section}{\numberline {2.3}Normal Forms}{10}{section.2.3}}
\newlabel{sec:relNF}{{\M@TitleReference {2.3}{Normal Forms}}{10}{Normal Forms}{section.2.3}{}}
\citation{1982zaniolo,1995databases}
\citation{1974codd}
\citation{1995databases}
\citation{1995databases}
\citation{1992mannila}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.3.1}Third Normal Form}{11}{subsection.2.3.1}}
\newlabel{def:3NF}{{\M@TitleReference {2.1}{Third Normal Form}}{11}{}{definitionx.2.1}{}}
\newlabel{ex:3NF}{{\M@TitleReference {2.1}{Third Normal Form}}{11}{}{examplex.2.1}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.3.2}Boyce-Codd Normal Form}{11}{subsection.2.3.2}}
\newlabel{ex:BCNF}{{\M@TitleReference {2.2}{Boyce-Codd Normal Form}}{11}{}{examplex.2.2}{}}
\citation{1995databases}
\@writefile{lof}{\contentsline {figure}{\numberline {2.2}{\ignorespaces Relation $course$ in 3NF\relax }}{12}{figure.caption.12}}
\newlabel{fig:relCourse3NF}{{\M@TitleReference {2.2}{Relation $course$ in 3NF\relax }}{12}{Relation $course$ in 3NF\relax }{figure.caption.12}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {2.3}{\ignorespaces Relation $course$ and $rooms$ in BCNF\relax }}{12}{figure.caption.13}}
\newlabel{fig:relCourseBCNF}{{\M@TitleReference {2.3}{Relation $course$ and $rooms$ in BCNF\relax }}{12}{Relation $course$ and $rooms$ in BCNF\relax }{figure.caption.13}{}}
\@writefile{toc}{\contentsline {section}{\numberline {2.4}Summary}{13}{section.2.4}}
\citation{2006xml}
\citation{2001xsd}
\citation{2004arenas}
\citation{2002arenas,2003arenas,2004arenas,2006arenas}
\@writefile{lof}{\addvspace {10pt}}
\@writefile{lot}{\addvspace {10pt}}
\@writefile{toc}{\contentsline {chapter}{\chapternumberline {3}Existing Normal Form For XML Data}{15}{chapter.3}}
\@writefile{loa}{\addvspace {10\p@ }}
\newlabel{ch:xml}{{\M@TitleReference {3}{Existing Normal Form For XML Data}}{15}{Existing Normal Form For XML Data}{chapter.3}{}}
\@writefile{toc}{\contentsline {paragraph}{XML Documents.}{15}{section*.14}}
\citation{2006xml}
\citation{2001xsd}
\citation{2006arenas2}
\citation{2001fanlibkin,2002fanlibkin}
\citation{2004arenas}
\@writefile{lof}{\contentsline {figure}{\numberline {3.1}{\ignorespaces An XML document with the same information as in Figure~\ref  {fig:relCourse}.\relax }}{16}{figure.caption.15}}
\newlabel{fig:xmlCourse}{{\M@TitleReference {3.1}{An XML document with the same information as in Figure~\ref  {fig:relCourse}.\relax }}{16}{An XML document with the same information as in Figure~\ref {fig:relCourse}.\relax }{figure.caption.15}{}}
\newlabel{ex:course_xml}{{\M@TitleReference {3.1}{XML Documents.}}{16}{}{examplex.3.1}{}}
\@writefile{toc}{\contentsline {paragraph}{Document Type Definitions (DTDs).}{16}{section*.16}}
\newlabel{ex:dtdCourse}{{\M@TitleReference {3.2}{Document Type Definitions (DTDs).}}{16}{}{examplex.3.2}{}}
\@writefile{toc}{\contentsline {section}{\numberline {3.1}Preliminaries}{16}{section.3.1}}
\newlabel{sec:xml_pre}{{\M@TitleReference {3.1}{Preliminaries}}{16}{Preliminaries}{section.3.1}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {3.2}{\ignorespaces A DTD representing courses\relax }}{17}{figure.caption.17}}
\newlabel{fig:dtdCourse}{{\M@TitleReference {3.2}{A DTD representing courses\relax }}{17}{A DTD representing courses\relax }{figure.caption.17}{}}
\citation{2004arenas}
\newlabel{def:DTD}{{\M@TitleReference {3.3}{Preliminaries}}{18}{}{definitionx.3.3}{}}
\newlabel{RF1}{19}
\@writefile{lof}{\contentsline {figure}{\numberline {3.3}{\ignorespaces The tree representation of the XML document in Figure~\ref  {fig:xmlCourse}.\relax }}{19}{figure.caption.18}}
\newlabel{fig:treeCourse}{{\M@TitleReference {3.3}{The tree representation of the XML document in Figure~\ref  {fig:xmlCourse}.\relax }}{19}{The tree representation of the XML document in Figure~\ref {fig:xmlCourse}.\relax }{figure.caption.18}{}}
\newlabel{ex:course_dtd}{{\M@TitleReference {3.4}{Preliminaries}}{20}{}{examplex.3.4}{}}
\citation{2004arenas}
\citation{2004arenas}
\newlabel{ex:xml_paths}{{\M@TitleReference {3.5}{Preliminaries}}{21}{}{examplex.3.5}{}}
\citation{2004arenas}
\citation{1995databases}
\@writefile{lof}{\contentsline {figure}{\numberline {3.4}{\ignorespaces A DTD mapped from the relational schema $course$\relax }}{22}{figure.caption.19}}
\newlabel{fig:dtdCourseMap}{{\M@TitleReference {3.4}{A DTD mapped from the relational schema $course$\relax }}{22}{A DTD mapped from the relational schema $course$\relax }{figure.caption.19}{}}
\@writefile{toc}{\contentsline {section}{\numberline {3.2}A Direct-Mapping From Relational Data To XML Documents}{22}{section.3.2}}
\newlabel{sec:xml_map}{{\M@TitleReference {3.2}{A Direct-Mapping From Relational Data To XML Documents}}{22}{A Direct-Mapping From Relational Data To XML Documents}{section.3.2}{}}
\newlabel{ex:dtdCourseMap}{{\M@TitleReference {3.6}{A Direct-Mapping From Relational Data To XML Documents}}{22}{}{examplex.3.6}{}}
\@writefile{toc}{\contentsline {section}{\numberline {3.3}Data Dependencies}{22}{section.3.3}}
\newlabel{sec:xml_fd}{{\M@TitleReference {3.3}{Data Dependencies}}{22}{Data Dependencies}{section.3.3}{}}
\citation{2004arenas}
\citation{2004arenas}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.3.1}Tree Tuples}{23}{subsection.3.3.1}}
\newlabel{def:treetuple}{{\M@TitleReference {3.6}{Tree Tuples}}{23}{}{definitionx.3.6}{}}
\newlabel{ex:treetuple}{{\M@TitleReference {3.7}{Tree Tuples}}{23}{}{examplex.3.7}{}}
\citation{2004arenas}
\citation{2004arenas}
\citation{2006arenas2}
\@writefile{lof}{\contentsline {figure}{\numberline {3.5}{\ignorespaces The XML tree $tree_D(t)$.\relax }}{24}{figure.caption.20}}
\newlabel{fig:tree_D}{{\M@TitleReference {3.5}{The XML tree $tree_D(t)$.\relax }}{24}{The XML tree $tree_D(t)$.\relax }{figure.caption.20}{}}
\newlabel{ex:tree_D}{{\M@TitleReference {3.8}{Tree Tuples}}{24}{}{examplex.3.8}{}}
\newlabel{ex:tuples}{{\M@TitleReference {3.9}{Tree Tuples}}{24}{}{examplex.3.9}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.3.2}XML Functional Dependencies}{25}{subsection.3.3.2}}
\newlabel{ex:XFDs}{{\M@TitleReference {3.10}{XML Functional Dependencies}}{25}{}{examplex.3.10}{}}
\newlabel{eqn:xfd_c1}{{3.1}{25}{}{equation.3.3.1}{}}
\newlabel{eqn:xfd_c2}{{3.2}{25}{}{equation.3.3.2}{}}
\newlabel{eqn:xfd_c3}{{3.3}{25}{}{equation.3.3.3}{}}
\citation{2006arenas2}
\citation{2004arenas,2006arenas2}
\citation{2004arenas}
\@writefile{lof}{\contentsline {figure}{\numberline {3.6}{\ignorespaces The XML tree $T_\nvDash $ that violates the XFD given in Equation~\ref  {eqn:xfd_c1}.\relax }}{26}{figure.caption.21}}
\newlabel{fig:xfd_viol}{{\M@TitleReference {3.6}{The XML tree $T_\nvDash $ that violates the XFD given in Equation~\ref  {eqn:xfd_c1}.\relax }}{26}{The XML tree $T_\nmodels $ that violates the XFD given in Equation~\ref {eqn:xfd_c1}.\relax }{figure.caption.21}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {3.3.2.1}Implication of XFDs}{26}{subsubsection.3.3.2.1}}
\newlabel{thm:XFDImpl}{{\M@TitleReference {3.1}{Implication of XFDs}}{26}{}{theorem.3.1}{}}
\citation{2004arenas}
\citation{2004arenas}
\citation{2004arenas}
\citation{2004arenas}
\citation{2004arenas}
\citation{1995databases}
\@writefile{toc}{\contentsline {paragraph}{Simple DTDs.}{27}{section*.22}}
\newlabel{thm:XFDImpl_simple}{{\M@TitleReference {3.2}{Simple DTDs.}}{27}{}{theorem.3.2}{}}
\@writefile{toc}{\contentsline {paragraph}{Relational DTDs.}{27}{section*.23}}
\newlabel{thm:XFDImpl_rel}{{\M@TitleReference {3.3}{Relational DTDs.}}{27}{}{theorem.3.3}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {3.3.2.2}Nonaxiomatizability of XFDs}{27}{subsubsection.3.3.2.2}}
\newlabel{prop:kaxiom}{{\M@TitleReference {3.1}{Nonaxiomatizability of XFDs}}{27}{}{proposition.3.1}{}}
\citation{2004arenas}
\citation{2004arenas}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {3.3.2.3}The Direct-Mapping of XFDs}{28}{subsubsection.3.3.2.3}}
\newlabel{eqn:xfd_c1_map}{{3.4}{28}{}{equation.3.3.4}{}}
\newlabel{eqn:xfd_c2_map}{{3.5}{28}{}{equation.3.3.5}{}}
\newlabel{eqn:xfd_c3_map}{{3.6}{28}{}{equation.3.3.6}{}}
\newlabel{eqn:xfd_map}{{3.7}{28}{}{equation.3.3.7}{}}
\@writefile{toc}{\contentsline {section}{\numberline {3.4}Normal Forms}{28}{section.3.4}}
\newlabel{sec:xml_nf}{{\M@TitleReference {3.4}{Normal Forms}}{28}{Normal Forms}{section.3.4}{}}
\citation{2003ley}
\citation{2004arenas}
\citation{2003ley}
\citation{2004arenas}
\citation{2004arenas}
\citation{2003ley}
\citation{2004arenas}
\citation{2004arenas}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.4.1}Redundancy in XML Documents}{29}{subsection.3.4.1}}
\newlabel{ex:dtdConf}{{\M@TitleReference {3.12}{Redundancy in XML Documents}}{29}{}{examplex.3.12}{}}
\newlabel{eqn:XFD_conf}{{3.8}{29}{}{equation.3.4.8}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.4.2}XML Normal Form}{29}{subsection.3.4.2}}
\newlabel{eqn:XFD_conf_XNF}{{3.9}{29}{}{equation.3.4.9}{}}
\newlabel{RF2}{30}
\@writefile{lof}{\contentsline {figure}{\numberline {3.7}{\ignorespaces The tree representation of the XML document in Figure~\ref  {fig:treeCourse} with a new element room, that removes a redundancy.\relax }}{30}{figure.caption.24}}
\newlabel{fig:treeCourseRoom}{{\M@TitleReference {3.7}{The tree representation of the XML document in Figure~\ref  {fig:treeCourse} with a new element room, that removes a redundancy.\relax }}{30}{The tree representation of the XML document in Figure~\ref {fig:treeCourse} with a new element room, that removes a redundancy.\relax }{figure.caption.24}{}}
\citation{2006arenas}
\citation{2005kolahi}
\@writefile{lof}{\contentsline {figure}{\numberline {3.8}{\ignorespaces Part of the DTD from the DBLP database \cite  {2003ley}, taken from \cite  {2004arenas}\relax }}{31}{figure.caption.25}}
\newlabel{fig:dtdConf}{{\M@TitleReference {3.8}{Part of the DTD from the DBLP database \cite  {2003ley}, taken from \cite  {2004arenas}\relax }}{31}{Part of the DTD from the DBLP database \cite {2003ley}, taken from \cite {2004arenas}\relax }{figure.caption.25}{}}
\newlabel{ex:XNFcourse}{{\M@TitleReference {3.14}{XML Normal Form}}{31}{}{examplex.3.14}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {3.9}{\ignorespaces A DTD originally mapped from the relational schema $course$, which is repaired to be in XNF\relax }}{32}{figure.caption.26}}
\newlabel{fig:dtdCourseXNF}{{\M@TitleReference {3.9}{A DTD originally mapped from the relational schema $course$, which is repaired to be in XNF\relax }}{32}{A DTD originally mapped from the relational schema $course$, which is repaired to be in XNF\relax }{figure.caption.26}{}}
\newlabel{eqn:xnf_1}{{3.10}{32}{}{equation.3.4.10}{}}
\newlabel{eqn:xnf_2}{{3.11}{32}{}{equation.3.4.11}{}}
\newlabel{eqn:xnf_3}{{3.12}{32}{}{equation.3.4.12}{}}
\newlabel{eqn:xnf_4}{{3.13}{32}{}{equation.3.4.13}{}}
\newlabel{eqn:xnf_5}{{3.14}{32}{}{equation.3.4.14}{}}
\newlabel{eqn:xnf_6}{{3.15}{32}{}{equation.3.4.15}{}}
\newlabel{eqn:xnf_7}{{3.16}{32}{}{equation.3.4.16}{}}
\newlabel{RF3}{33}
\@writefile{lof}{\contentsline {figure}{\numberline {3.10}{\ignorespaces A redundancy free XML tree with the same information as in Figure~\ref  {fig:relCourse}.\relax }}{33}{figure.caption.27}}
\newlabel{fig:XNFcourse}{{\M@TitleReference {3.10}{A redundancy free XML tree with the same information as in Figure~\ref  {fig:relCourse}.\relax }}{33}{A redundancy free XML tree with the same information as in Figure~\ref {fig:relCourse}.\relax }{figure.caption.27}{}}
\citation{2004arenas}
\citation{2004arenas}
\citation{1996mok}
\citation{2004arenas}
\citation{2006arenas}
\citation{2004arenas}
\citation{2004arenas}
\@writefile{toc}{\contentsline {paragraph}{The Complexity of Testing XNF.}{34}{section*.28}}
\@writefile{toc}{\contentsline {section}{\numberline {3.5}Summary}{34}{section.3.5}}
\citation{2001semanticweb,2006semanticweb}
\citation{2004rdf}
\citation{2010foundsemweb}
\citation{2004rdfs}
\@writefile{lof}{\addvspace {10pt}}
\@writefile{lot}{\addvspace {10pt}}
\@writefile{toc}{\contentsline {chapter}{\chapternumberline {4}A New Normal Form For Description Logics}{37}{chapter.4}}
\@writefile{loa}{\addvspace {10\p@ }}
\newlabel{ch:dl}{{\M@TitleReference {4}{A New Normal Form For Description Logics}}{37}{A New Normal Form For Description Logics}{chapter.4}{}}
\citation{2012owl}
\citation{2012owl2semantics}
\citation{2012owl2prof}
\citation{2005berardi,2009calvanese}
\citation{2003baader}
\citation{2003baader,2009baader}
\@writefile{toc}{\contentsline {section}{\numberline {4.1}Preliminaries}{38}{section.4.1}}
\newlabel{sec:dl_pre}{{\M@TitleReference {4.1}{Preliminaries}}{38}{Preliminaries}{section.4.1}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.1.1}The Description Logic $\textit  {DL-Lite}_\mathcal  {A}$}{38}{subsection.4.1.1}}
\citation{2006calvanese,2008poggi}
\citation{2007calvanese2,2009artale,2013calvanese}
\citation{2006calvanese}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.1.1.1}Syntax of $\textit  {DL-Lite}_\mathcal  {A}$}{39}{subsubsection.4.1.1.1}}
\newlabel{ex:dl_terms}{{\M@TitleReference {4.1}{Syntax of $\textit  {DL-Lite}_\mathcal  {A}$}}{39}{}{examplex.4.1}{}}
\citation{2008poggi}
\newlabel{ex:dl_tbox}{{\M@TitleReference {4.2}{Syntax of $\textit  {DL-Lite}_\mathcal  {A}$}}{40}{}{examplex.4.2}{}}
\newlabel{ex:dl_abox}{{\M@TitleReference {4.3}{Syntax of $\textit  {DL-Lite}_\mathcal  {A}$}}{41}{}{examplex.4.3}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {4.1}{\ignorespaces A graph representation of the ABox $\mathcal  {A}_c$.\relax }}{42}{figure.caption.29}}
\newlabel{fig:ABox_course}{{\M@TitleReference {4.1}{A graph representation of the ABox $\mathcal  {A}_c$.\relax }}{42}{A graph representation of the ABox $\mcA _c$.\relax }{figure.caption.29}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.1.1.2}Semantics of $\textit  {DL-Lite}_\mathcal  {A}$}{42}{subsubsection.4.1.1.2}}
\newlabel{ex:dl_int}{{\M@TitleReference {4.4}{Semantics of $\textit  {DL-Lite}_\mathcal  {A}$}}{43}{}{examplex.4.4}{}}
\citation{2009calvanese}
\citation{2009calvanese}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.1.1.3}Queries over $\textit  {DL-Lite}_\mathcal  {A}$ KB}{44}{subsubsection.4.1.1.3}}
\citation{2009calvanese}
\citation{2009calvanese}
\citation{2009calvanese}
\citation{2009calvanese}
\citation{2009calvanese}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.1.1.4}Reasoning in $\textit  {DL-Lite}_\mathcal  {A}$}{45}{subsubsection.4.1.1.4}}
\citation{1984johnson,1995databases}
\citation{2009calvanese}
\citation{2009calvanese}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.1.2}Reasoning over $\textit  {DL-Lite}_\mathcal  {A}$ KB}{46}{subsection.4.1.2}}
\citation{2009calvanese}
\citation{2009calvanese}
\citation{2006calvanese}
\citation{2009calvanese}
\citation{2009calvanese}
\citation{2009calvanese}
\citation{2009calvanese}
\citation{2009calvanese}
\citation{2009calvanese}
\citation{2009calvanese}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.1.3}Universal Model}{49}{subsection.4.1.3}}
\citation{2006kharlamov,1995databases}
\citation{2006kharlamov}
\citation{2006kharlamov}
\citation{2005fagin}
\citation{2006kharlamov}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.1.4}Query Answering over finite interpretations}{50}{subsection.4.1.4}}
\citation{2006kharlamov}
\citation{2005fagin}
\@writefile{lof}{\contentsline {figure}{\numberline {4.2}{\ignorespaces A dependency graph $G_{\mathcal  {K}^\prime }$ with a cycle (in \leavevmode {\color  {red}red}) that contains a $*$-labeled edge \relax }}{51}{figure.caption.30}}
\newlabel{fig:depGraph}{{\M@TitleReference {4.2}{A dependency graph $G_{\mathcal  {K}^\prime }$ with a cycle (in \leavevmode {\color  {red}red}) that contains a $*$-labeled edge \relax }}{51}{A dependency graph $G_{\mcK ^\prime }$ with a cycle (in \textcolor {red}{red}) that contains a $*$-labeled edge \relax }{figure.caption.30}{}}
\citation{2009calvanese}
\citation{2009calvanese}
\citation{2009calvanese}
\citation{2009calvanese}
\citation{2009calvanese}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.1.5}Query Answering over infinite interpretations}{52}{subsection.4.1.5}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.1.5.1}Query Reformulation}{52}{subsubsection.4.1.5.1}}
\@writefile{lot}{\contentsline {table}{\numberline {4.1}{\ignorespaces The result $gr(g,\alpha )$ of applying a positive inclusion $\alpha $ to an atom $g$ (Fig. 12 adapted from \cite  {2009calvanese})\relax }}{52}{table.caption.31}}
\newlabel{tag:gr}{{\M@TitleReference {4.1}{The result $gr(g,\alpha )$ of applying a positive inclusion $\alpha $ to an atom $g$ (Fig. 12 adapted from \cite  {2009calvanese})\relax }}{52}{The result $gr(g,\alpha )$ of applying a positive inclusion $\alpha $ to an atom $g$ (Fig. 12 adapted from \cite {2009calvanese})\relax }{table.caption.31}{}}
\citation{2009calvanese}
\citation{2009calvanese}
\citation{2009calvanese}
\@writefile{loa}{\contentsline {algocf}{\numberline {4.1}{\ignorespaces The algorithm \textsf  {PerfectRef} that computes the perfect reformulation of a CQ w.r.t. a $\textit  {DL-Lite}_\mathcal  {A}$ TBox (Fig. 13 from \cite  {2009calvanese})\relax }}{53}{algocf.4.1}}
\newlabel{alg:dl_perfectref}{{\M@TitleReference {4.1}{Query Reformulation}}{53}{Query Reformulation}{algocf.4.1}{}}
\newlabel{ex:perfect_ref}{{\M@TitleReference {4.7}{Query Reformulation}}{53}{}{examplex.4.7}{}}
\citation{2009calvanese}
\citation{2012sangiorgi}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.1.6}Additional Notions}{54}{subsection.4.1.6}}
\citation{2012rdbmapping}
\citation{2012Sequeda}
\citation{2012rdbmapping}
\newlabel{def:bisim}{{\M@TitleReference {4.12}{Additional Notions}}{55}{}{definitionx.4.12}{}}
\@writefile{toc}{\contentsline {section}{\numberline {4.2}A Direct Mapping of Relational Data to Description Logic Knowledge Bases}{55}{section.4.2}}
\newlabel{sec:dl_map}{{\M@TitleReference {4.2}{A Direct Mapping of Relational Data to Description Logic Knowledge Bases}}{55}{A Direct Mapping of Relational Data to Description Logic Knowledge Bases}{section.4.2}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.2.1}A Direct Mapping of Relational Data to RDF}{55}{subsection.4.2.1}}
\citation{2012rdbmapping}
\citation{2012Sequeda}
\citation{2012rdbmapping}
\citation{2012Sequeda}
\@writefile{lof}{\contentsline {figure}{\numberline {4.3}{\ignorespaces The RDF triples obtained by the RDB-direct-mapping \cite  {2012rdbmapping} from the relational table in Figure~\ref  {fig:relCourse3NF}. In \leavevmode {\color  {red}red} are the triples that are in the result of the RDB-direct-mapping but not in the result of the direct mapping $\mathcal  {D}\mathcal  {M}$ \cite  {2012Sequeda}, which will be introduced next.\relax }}{56}{figure.caption.33}}
\newlabel{fig:RDFCourse}{{\M@TitleReference {4.3}{The RDF triples obtained by the RDB-direct-mapping \cite  {2012rdbmapping} from the relational table in Figure~\ref  {fig:relCourse3NF}. In \leavevmode {\color  {red}red} are the triples that are in the result of the RDB-direct-mapping but not in the result of the direct mapping $\mathcal  {D}\mathcal  {M}$ \cite  {2012Sequeda}, which will be introduced next.\relax }}{56}{The RDF triples obtained by the RDB-direct-mapping \cite {2012rdbmapping} from the relational table in Figure~\ref {fig:relCourse3NF}. In \textcolor {red}{red} are the triples that are in the result of the RDB-direct-mapping but not in the result of the direct mapping $\mcD \mcM $ \cite {2012Sequeda}, which will be introduced next.\relax }{figure.caption.33}{}}
\citation{2012Sequeda}
\citation{2012Sequeda}
\@writefile{toc}{\contentsline {paragraph}{Fundamental properties}{57}{section*.34}}
\@writefile{toc}{\contentsline {paragraph}{Desirable properties}{57}{section*.35}}
\citation{2012Sequeda}
\citation{2012Sequeda}
\citation{2012Sequeda}
\citation{2012Sequeda}
\@writefile{lof}{\contentsline {figure}{\numberline {4.4}{\ignorespaces The RDF triples obtained by the direct mapping $\mathcal  {D}\mathcal  {M}$ \cite  {2012Sequeda} from the relational table in Figure~\ref  {fig:relCourse3NF}. In \leavevmode {\color  {darkgreen}green} are the triples that are in the result of the direct mapping $\mathcal  {D}\mathcal  {M}$ but not in the RDB-direct-mapping.\relax }}{59}{figure.caption.36}}
\newlabel{fig:RDF2Course}{{\M@TitleReference {4.4}{The RDF triples obtained by the direct mapping $\mathcal  {D}\mathcal  {M}$ \cite  {2012Sequeda} from the relational table in Figure~\ref  {fig:relCourse3NF}. In \leavevmode {\color  {darkgreen}green} are the triples that are in the result of the direct mapping $\mathcal  {D}\mathcal  {M}$ but not in the RDB-direct-mapping.\relax }}{59}{The RDF triples obtained by the direct mapping $\mcD \mcM $ \cite {2012Sequeda} from the relational table in Figure~\ref {fig:relCourse3NF}. In \textcolor {darkgreen}{green} are the triples that are in the result of the direct mapping $\mcD \mcM $ but not in the RDB-direct-mapping.\relax }{figure.caption.36}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.2.2}A Direct Mapping of Relational Data to $\textit  {DL-Lite}_\mathcal  {A}$ Knowledge Bases}{59}{subsection.4.2.2}}
\newlabel{ssec:dl_map_rdm}{{\M@TitleReference {4.2.2}{A Direct Mapping of Relational Data to $\textit  {DL-Lite}_\mathcal  {A}$ Knowledge Bases}}{59}{A Direct Mapping of Relational Data to $\DLA $ Knowledge Bases}{subsection.4.2.2}{}}
\newlabel{def:dl_sm}{{\M@TitleReference {4.13}{A Direct Mapping of Relational Data to $\textit  {DL-Lite}_\mathcal  {A}$ Knowledge Bases}}{60}{}{definitionx.4.13}{}}
\newlabel{ex:sm_transl}{{\M@TitleReference {4.8}{A Direct Mapping of Relational Data to $\textit  {DL-Lite}_\mathcal  {A}$ Knowledge Bases}}{60}{}{examplex.4.8}{}}
\citation{2005berardi}
\newlabel{ex:im_transl}{{\M@TitleReference {4.9}{A Direct Mapping of Relational Data to $\textit  {DL-Lite}_\mathcal  {A}$ Knowledge Bases}}{62}{}{examplex.4.9}{}}
\newlabel{lem:i2m_sound}{{\M@TitleReference {4.4}{A Direct Mapping of Relational Data to $\textit  {DL-Lite}_\mathcal  {A}$ Knowledge Bases}}{62}{}{lemma.4.4}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {4.5}{\ignorespaces An interpretation translated by the function $\mathit  {i2m}$ from the instance given in Figure~\ref  {fig:relCourse3NF}.\relax }}{63}{figure.caption.37}}
\newlabel{fig:im_transl}{{\M@TitleReference {4.5}{An interpretation translated by the function $\mathit  {i2m}$ from the instance given in Figure~\ref  {fig:relCourse3NF}.\relax }}{63}{An interpretation translated by the function $\ffo {i2m}$ from the instance given in Figure~\ref {fig:relCourse3NF}.\relax }{figure.caption.37}{}}
\newlabel{lem:m2i_sound}{{\M@TitleReference {4.5}{A Direct Mapping of Relational Data to $\textit  {DL-Lite}_\mathcal  {A}$ Knowledge Bases}}{64}{}{lemma.4.5}{}}
\newlabel{lem:drm_instance}{{\M@TitleReference {4.6}{A Direct Mapping of Relational Data to $\textit  {DL-Lite}_\mathcal  {A}$ Knowledge Bases}}{64}{}{lemma.4.6}{}}
\newlabel{lem:drm_model}{{\M@TitleReference {4.7}{A Direct Mapping of Relational Data to $\textit  {DL-Lite}_\mathcal  {A}$ Knowledge Bases}}{65}{}{lemma.4.7}{}}
\newlabel{ex:m2i_iso}{{\M@TitleReference {4.10}{A Direct Mapping of Relational Data to $\textit  {DL-Lite}_\mathcal  {A}$ Knowledge Bases}}{65}{}{examplex.4.10}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {4.6}{\ignorespaces The model $\mathcal  {M}_{course}$.\relax }}{66}{figure.caption.38}}
\newlabel{fig:im_iso}{{\M@TitleReference {4.6}{The model $\mathcal  {M}_{course}$.\relax }}{66}{The model $\mcM _{course}$.\relax }{figure.caption.38}{}}
\citation{2008calvanese}
\citation{2008calvanese}
\newlabel{cor:mappingSemantics}{{\M@TitleReference {4.1}{A Direct Mapping of Relational Data to $\textit  {DL-Lite}_\mathcal  {A}$ Knowledge Bases}}{67}{}{corollary.4.1}{}}
\@writefile{toc}{\contentsline {section}{\numberline {4.3}Data Dependencies}{67}{section.4.3}}
\newlabel{sec:dl_fd}{{\M@TitleReference {4.3}{Data Dependencies}}{67}{Data Dependencies}{section.4.3}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.3.1}Path-based identification constraints}{67}{subsection.4.3.1}}
\newlabel{ssec:dl_fd_pidc}{{\M@TitleReference {4.3.1}{Path-based identification constraints}}{67}{Path-based identification constraints}{subsection.4.3.1}{}}
\citation{2008calvanese,2009calvanese}
\citation{2008calvanese}
\citation{2008calvanese}
\citation{2009calvanese}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.3.1.1}KB satisfiability with pIdCs}{69}{subsubsection.4.3.1.1}}
\newlabel{sssec:pidcs_sat}{{\M@TitleReference {4.3.1.1}{KB satisfiability with pIdCs}}{69}{KB satisfiability with pIdCs}{subsubsection.4.3.1.1}{}}
\newlabel{thm:pIdCs_sat}{{\M@TitleReference {4.4}{KB satisfiability with pIdCs}}{70}{}{theorem.4.4}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.3.1.2}Implication of pIdCs}{70}{subsubsection.4.3.1.2}}
\newlabel{sssec:pidcs_impl}{{\M@TitleReference {4.3.1.2}{Implication of pIdCs}}{70}{Implication of pIdCs}{subsubsection.4.3.1.2}{}}
\@writefile{loa}{\contentsline {algocf}{\numberline {4.2}{\ignorespaces The algorithm \textsf  {IdCImpl} for deciding the implication of pIdCs\relax }}{71}{algocf.4.2}}
\newlabel{alg:pIdC_impl}{{\M@TitleReference {4.2}{Implication of pIdCs}}{71}{Implication of pIdCs}{algocf.4.2}{}}
\newlabel{ex:pIdC_Impl1}{{\M@TitleReference {4.11}{Implication of pIdCs}}{71}{}{examplex.4.11}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {4.7}{\ignorespaces The counter-model ABox $\mathcal  {A}_\alpha $.\relax }}{72}{figure.caption.40}}
\newlabel{fig:ex_pIdC_Impl1}{{\M@TitleReference {4.7}{The counter-model ABox $\mathcal  {A}_\alpha $.\relax }}{72}{The counter-model ABox $\mcA _\alpha $.\relax }{figure.caption.40}{}}
\newlabel{ex:pIdC_Impl2}{{\M@TitleReference {4.12}{Implication of pIdCs}}{72}{}{examplex.4.12}{}}
\citation{1995databases,2005fagin}
\citation{1995databases,2005fagin}
\@writefile{lof}{\contentsline {figure}{\numberline {4.8}{\ignorespaces The chase of the KB $\mathcal  {K}= \left <\mathcal  {T},\mathcal  {A}_\alpha \right >$ adds the membership assertions drawn in \leavevmode {\color  {red}red}.\relax }}{73}{figure.caption.41}}
\newlabel{fig:ex_pIdC_Impl2}{{\M@TitleReference {4.8}{The chase of the KB $\mathcal  {K}= \left <\mathcal  {T},\mathcal  {A}_\alpha \right >$ adds the membership assertions drawn in \leavevmode {\color  {red}red}.\relax }}{73}{The chase of the KB $\mcK = \left <\mcT ,\mcA _\alpha \right >$ adds the membership assertions drawn in \textcolor {red}{red}.\relax }{figure.caption.41}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {4.9}{\ignorespaces The ABox after we have applied the pIdC $\left (\unhbox \voidb@x \hbox {id} \tmspace  +\thickmuskip {.2777em}\tmspace  +\thickmuskip {.2777em} \exists P^- \tmspace  +\thickmuskip {.2777em}\tmspace  +\thickmuskip {.2777em} P^- \circ S \circ P\right )$.\relax }}{73}{figure.caption.42}}
\newlabel{fig:ex_pIdC_Impl3}{{\M@TitleReference {4.9}{The ABox after we have applied the pIdC $\left (\unhbox \voidb@x \hbox {id} \tmspace  +\thickmuskip {.2777em}\tmspace  +\thickmuskip {.2777em} \exists P^- \tmspace  +\thickmuskip {.2777em}\tmspace  +\thickmuskip {.2777em} P^- \circ S \circ P\right )$.\relax }}{73}{The ABox after we have applied the pIdC $\id {\exists P^-}{P^- \circ S \circ P}$.\relax }{figure.caption.42}{}}
\newlabel{thm:pidcs_impl}{{\M@TitleReference {4.5}{Implication of pIdCs}}{73}{}{theorem.4.5}{}}
\newlabel{fig:ex_pIdC_I1}{{\M@TitleReference {4.10a}{Instance $\mathit  {I}_1$: $\mathit  {I}_1 \vDash A \rightarrow B$\relax }}{74}{Instance $\ifo {I}_1$: $\ifo {I}_1 \models A \ra B$\relax }{figure.caption.43}{}}
\newlabel{sub@fig:ex_pIdC_I1}{{\M@TitleReference {a}{Instance $\mathit  {I}_1$: $\mathit  {I}_1 \vDash A \rightarrow B$\relax }}{74}{Instance $\ifo {I}_1$: $\ifo {I}_1 \models A \ra B$\relax }{figure.caption.43}{}}
\newlabel{fig:ex_pIdC_I2}{{\M@TitleReference {4.10b}{Instance $\mathit  {I}_2$: $\mathit  {I}_2 \nvDash A \rightarrow B$\relax }}{74}{Instance $\ifo {I}_2$: $\ifo {I}_2 \nmodels A \ra B$\relax }{figure.caption.43}{}}
\newlabel{sub@fig:ex_pIdC_I2}{{\M@TitleReference {b}{Instance $\mathit  {I}_2$: $\mathit  {I}_2 \nvDash A \rightarrow B$\relax }}{74}{Instance $\ifo {I}_2$: $\ifo {I}_2 \nmodels A \ra B$\relax }{figure.caption.43}{}}
\newlabel{fig:ex_pIdC_M1}{{\M@TitleReference {4.10c}{Model $\mathcal  {M}_1 = \mathit  {i2m}_{R\left [U\right ]}\left (\mathit  {I}_1\right )$: \newline  $\mathcal  {M}_1 \vDash \left (\unhbox \voidb@x \hbox {id} \tmspace  +\thickmuskip {.2777em}\tmspace  +\thickmuskip {.2777em} R\_B \tmspace  +\thickmuskip {.2777em}\tmspace  +\thickmuskip {.2777em} R\#B^- \circ R\#A\right )$\relax }}{74}{Model $\mfo {M}_1 = \ffo {i2m}_{R\left [U\right ]}\left (\ifo {I}_1\right )$: \newline $\mfo {M}_1 \models \id {R\_B}{R\#B^- \circ R\#A}$\relax }{figure.caption.43}{}}
\newlabel{sub@fig:ex_pIdC_M1}{{\M@TitleReference {c}{Model $\mathcal  {M}_1 = \mathit  {i2m}_{R\left [U\right ]}\left (\mathit  {I}_1\right )$: \newline  $\mathcal  {M}_1 \vDash \left (\unhbox \voidb@x \hbox {id} \tmspace  +\thickmuskip {.2777em}\tmspace  +\thickmuskip {.2777em} R\_B \tmspace  +\thickmuskip {.2777em}\tmspace  +\thickmuskip {.2777em} R\#B^- \circ R\#A\right )$\relax }}{74}{Model $\mfo {M}_1 = \ffo {i2m}_{R\left [U\right ]}\left (\ifo {I}_1\right )$: \newline $\mfo {M}_1 \models \id {R\_B}{R\#B^- \circ R\#A}$\relax }{figure.caption.43}{}}
\newlabel{fig:ex_pIdC_M2}{{\M@TitleReference {4.10d}{Model $\mathcal  {M}_2 = \mathit  {i2m}_{R\left [U\right ]}\left (\mathit  {I}_2\right )$: \newline  $\mathcal  {M}_2 \nvDash \left (\unhbox \voidb@x \hbox {id} \tmspace  +\thickmuskip {.2777em}\tmspace  +\thickmuskip {.2777em} R\_B \tmspace  +\thickmuskip {.2777em}\tmspace  +\thickmuskip {.2777em} R\#B^- \circ R\#A\right )$\relax }}{74}{Model $\mfo {M}_2 = \ffo {i2m}_{R\left [U\right ]}\left (\ifo {I}_2\right )$: \newline $\mfo {M}_2 \nmodels \id {R\_B}{R\#B^- \circ R\#A}$\relax }{figure.caption.43}{}}
\newlabel{sub@fig:ex_pIdC_M2}{{\M@TitleReference {d}{Model $\mathcal  {M}_2 = \mathit  {i2m}_{R\left [U\right ]}\left (\mathit  {I}_2\right )$: \newline  $\mathcal  {M}_2 \nvDash \left (\unhbox \voidb@x \hbox {id} \tmspace  +\thickmuskip {.2777em}\tmspace  +\thickmuskip {.2777em} R\_B \tmspace  +\thickmuskip {.2777em}\tmspace  +\thickmuskip {.2777em} R\#B^- \circ R\#A\right )$\relax }}{74}{Model $\mfo {M}_2 = \ffo {i2m}_{R\left [U\right ]}\left (\ifo {I}_2\right )$: \newline $\mfo {M}_2 \nmodels \id {R\_B}{R\#B^- \circ R\#A}$\relax }{figure.caption.43}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {4.10}{\ignorespaces Instances and their mapping into $\textit  {DL-Lite}_\mathcal  {A}$ interpretations.\relax }}{74}{figure.caption.43}}
\newlabel{fig:ex_pIdC}{{\M@TitleReference {4.10}{Instances and their mapping into $\textit  {DL-Lite}_\mathcal  {A}$ interpretations.\relax }}{74}{Instances and their mapping into $\DLA $ interpretations.\relax }{figure.caption.43}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.3.1.3}Path-based IdCs as a formalism to model functional dependencies in $\textit  {DL-Lite}_\mathcal  {A}$}{74}{subsubsection.4.3.1.3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.3.2}FDs and pIdCs are semantically different}{74}{subsection.4.3.2}}
\newlabel{ssec:dl_fd_sem}{{\M@TitleReference {4.3.2}{FDs and pIdCs are semantically different}}{74}{FDs and pIdCs are semantically different}{subsection.4.3.2}{}}
\newlabel{fig:FD_IdC_I1}{{\M@TitleReference {4.11a}{Instance $\mathit  {I}_1$: $\mathit  {I}_1 \vDash \sigma $\relax }}{75}{Instance $\ifo {I}_1$: $\ifo {I}_1 \models \sigma $\relax }{figure.caption.44}{}}
\newlabel{sub@fig:FD_IdC_I1}{{\M@TitleReference {a}{Instance $\mathit  {I}_1$: $\mathit  {I}_1 \vDash \sigma $\relax }}{75}{Instance $\ifo {I}_1$: $\ifo {I}_1 \models \sigma $\relax }{figure.caption.44}{}}
\newlabel{fig:FD_IdC_I2}{{\M@TitleReference {4.11b}{Instance $\mathit  {I}_2$: $\mathit  {I}_2 \nvDash \sigma $\relax }}{75}{Instance $\ifo {I}_2$: $\ifo {I}_2 \nmodels \sigma $\relax }{figure.caption.44}{}}
\newlabel{sub@fig:FD_IdC_I2}{{\M@TitleReference {b}{Instance $\mathit  {I}_2$: $\mathit  {I}_2 \nvDash \sigma $\relax }}{75}{Instance $\ifo {I}_2$: $\ifo {I}_2 \nmodels \sigma $\relax }{figure.caption.44}{}}
\newlabel{fig:FD_IdC_M1}{{\M@TitleReference {4.11c}{Model $\mathcal  {M}_1 = \mathit  {i2m}_{R\left [U\right ]}\left (\mathit  {I}_1\right )$: $\mathcal  {M}_1 \nvDash \delta $\relax }}{75}{Model $\mfo {M}_1 = \ffo {i2m}_{R\left [U\right ]}\left (\ifo {I}_1\right )$: $\mfo {M}_1 \nmodels \delta $\relax }{figure.caption.44}{}}
\newlabel{sub@fig:FD_IdC_M1}{{\M@TitleReference {c}{Model $\mathcal  {M}_1 = \mathit  {i2m}_{R\left [U\right ]}\left (\mathit  {I}_1\right )$: $\mathcal  {M}_1 \nvDash \delta $\relax }}{75}{Model $\mfo {M}_1 = \ffo {i2m}_{R\left [U\right ]}\left (\ifo {I}_1\right )$: $\mfo {M}_1 \nmodels \delta $\relax }{figure.caption.44}{}}
\newlabel{fig:FD_IdC_M2}{{\M@TitleReference {4.11d}{Model $\mathcal  {M}_2 = \mathit  {i2m}_{R\left [U\right ]}\left (\mathit  {I}_2\right )$: $\mathcal  {M}_2 \nvDash \delta $\relax }}{75}{Model $\mfo {M}_2 = \ffo {i2m}_{R\left [U\right ]}\left (\ifo {I}_2\right )$: $\mfo {M}_2 \nmodels \delta $\relax }{figure.caption.44}{}}
\newlabel{sub@fig:FD_IdC_M2}{{\M@TitleReference {d}{Model $\mathcal  {M}_2 = \mathit  {i2m}_{R\left [U\right ]}\left (\mathit  {I}_2\right )$: $\mathcal  {M}_2 \nvDash \delta $\relax }}{75}{Model $\mfo {M}_2 = \ffo {i2m}_{R\left [U\right ]}\left (\ifo {I}_2\right )$: $\mfo {M}_2 \nmodels \delta $\relax }{figure.caption.44}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {4.11}{\ignorespaces Instances and their mapping into RDF graphs. The FD $AB \rightarrow C$ can distinguish the two structures $\mathit  {I}_1$ and $\mathit  {I}_2$, whereas the pIdC $\left (\unhbox \voidb@x \hbox {id} \tmspace  +\thickmuskip {.2777em}\tmspace  +\thickmuskip {.2777em} R\_C \tmspace  +\thickmuskip {.2777em}\tmspace  +\thickmuskip {.2777em} R\# C^- \circ R\# A, R\# C^- \circ R\# B\right )$ cannot distinguish the two models $\mathcal  {M}_1$ and $\mathcal  {M}_2$.\relax }}{75}{figure.caption.44}}
\newlabel{fig:FD_IdC}{{\M@TitleReference {4.11}{Instances and their mapping into RDF graphs. The FD $AB \rightarrow C$ can distinguish the two structures $\mathit  {I}_1$ and $\mathit  {I}_2$, whereas the pIdC $\left (\unhbox \voidb@x \hbox {id} \tmspace  +\thickmuskip {.2777em}\tmspace  +\thickmuskip {.2777em} R\_C \tmspace  +\thickmuskip {.2777em}\tmspace  +\thickmuskip {.2777em} R\# C^- \circ R\# A, R\# C^- \circ R\# B\right )$ cannot distinguish the two models $\mathcal  {M}_1$ and $\mathcal  {M}_2$.\relax }}{75}{Instances and their mapping into RDF graphs. The FD $AB \ra C$ can distinguish the two structures $\ifo {I}_1$ and $\ifo {I}_2$, whereas the pIdC $\id {R\_C}{R\# C^- \circ R\# A, R\# C^- \circ R\# B}$ cannot distinguish the two models $\mfo {M}_1$ and $\mfo {M}_2$.\relax }{figure.caption.44}{}}
\newlabel{ex:FD_IdC}{{\M@TitleReference {4.14}{FDs and pIdCs are semantically different}}{75}{}{examplex.4.14}{}}
\newlabel{thm:FdIdCmismatch}{{\M@TitleReference {4.6}{FDs and pIdCs are semantically different}}{75}{}{theorem.4.6}{}}
\newlabel{clm:bisim_path}{{\M@TitleReference {4.1}{FDs and pIdCs are semantically different}}{76}{}{claim.4.1}{}}
\newlabel{clm:bisim_instances}{{\M@TitleReference {4.2}{FDs and pIdCs are semantically different}}{76}{}{claim.4.2}{}}
\@writefile{lot}{\contentsline {table}{\numberline {4.2}{\ignorespaces Bisimulation relation of $\mathcal  {M}_1 \sim _\mathcal  {B}\mathcal  {M}_2$\relax }}{76}{table.caption.45}}
\newlabel{tab:biSim}{{\M@TitleReference {4.2}{Bisimulation relation of $\mathcal  {M}_1 \sim _\mathcal  {B}\mathcal  {M}_2$\relax }}{76}{Bisimulation relation of $\mfo {M}_1 \sim _\mcB \mfo {M}_2$\relax }{table.caption.45}{}}
\citation{2008calvanese}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.3.3}Tree-based identification constraints}{78}{subsection.4.3.3}}
\newlabel{ssec:dl_fd_tidc}{{\M@TitleReference {4.3.3}{Tree-based identification constraints}}{78}{Tree-based identification constraints}{subsection.4.3.3}{}}
\newlabel{ex:treeIdC}{{\M@TitleReference {4.15}{Tree-based identification constraints}}{79}{}{examplex.4.15}{}}
\newlabel{eqn:treeIdC}{{4.36}{79}{}{equation.4.3.36}{}}
\@writefile{lot}{\contentsline {table}{\numberline {4.3}{\ignorespaces Evaluation of the tIdC given in Equation~\ref  {eqn:treeIdC} over the interpretation in Figure ~\ref  {fig:FD_IdC_M1}\relax }}{80}{table.caption.46}}
\newlabel{tab:tIdC_M1}{{\M@TitleReference {4.3}{Evaluation of the tIdC given in Equation~\ref  {eqn:treeIdC} over the interpretation in Figure ~\ref  {fig:FD_IdC_M1}\relax }}{80}{Evaluation of the tIdC given in Equation~\ref {eqn:treeIdC} over the interpretation in Figure ~\ref {fig:FD_IdC_M1}\relax }{table.caption.46}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.3.3.1}KB satisfiability with tIdCs}{80}{subsubsection.4.3.3.1}}
\newlabel{sssec:tidcs_sat}{{\M@TitleReference {4.3.3.1}{KB satisfiability with tIdCs}}{80}{KB satisfiability with tIdCs}{subsubsection.4.3.3.1}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.3.3.2}Implication of tIdCs}{81}{subsubsection.4.3.3.2}}
\newlabel{sssec:tidcs_impl}{{\M@TitleReference {4.3.3.2}{Implication of tIdCs}}{81}{Implication of tIdCs}{subsubsection.4.3.3.2}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.3.3.3}The Direct-Mapping of FDs to IdCs}{82}{subsubsection.4.3.3.3}}
\newlabel{ex:dm_transl}{{\M@TitleReference {4.16}{The Direct-Mapping of FDs to IdCs}}{82}{}{examplex.4.16}{}}
\newlabel{ex:rdm_transl}{{\M@TitleReference {4.17}{The Direct-Mapping of FDs to IdCs}}{82}{}{examplex.4.17}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {4.12}{\ignorespaces Submodel of $\mathcal  {M}$, which violates $\varphi $\relax }}{83}{figure.caption.47}}
\newlabel{fig:fd_lemma}{{\M@TitleReference {4.12}{Submodel of $\mathcal  {M}$, which violates $\varphi $\relax }}{83}{Submodel of $\mfo {M}$, which violates $\varphi $\relax }{figure.caption.47}{}}
\newlabel{thm:inst_fdmap}{{\M@TitleReference {4.9}{The Direct-Mapping of FDs to IdCs}}{83}{}{theorem.4.9}{}}
\newlabel{cor:model_idcmap}{{\M@TitleReference {4.3}{The Direct-Mapping of FDs to IdCs}}{84}{}{corollary.4.3}{}}
\@writefile{toc}{\contentsline {section}{\numberline {4.4}Normal Forms}{84}{section.4.4}}
\newlabel{sec:dl_nf}{{\M@TitleReference {4.4}{Normal Forms}}{84}{Normal Forms}{section.4.4}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.4.1}Redundancy in $\textit  {DL-Lite}_{\mathcal  {A},tid}$ KBs}{84}{subsection.4.4.1}}
\newlabel{eqn:tidc_course}{{4.37}{84}{Redundancy in $\DLAtid $ KBs}{equation.4.4.37}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.4.2}$\textit  {DL-Lite}_{\mathcal  {A},tid}$ Normal Form}{85}{subsection.4.4.2}}
\newlabel{def:DLNF}{{\M@TitleReference {4.24}{$\textit  {DL-Lite}_{\mathcal  {A},tid}$ Normal Form}}{85}{}{definitionx.4.24}{}}
\newlabel{ex:DLNFcourse}{{\M@TitleReference {4.19}{$\textit  {DL-Lite}_{\mathcal  {A},tid}$ Normal Form}}{86}{}{examplex.4.19}{}}
\newlabel{eqn:room_tidc}{{4.40}{86}{}{equation.4.4.40}{}}
\citation{2008calvanese}
\citation{2008calvanese}
\citation{2008calvanese}
\citation{2008calvanese}
\citation{2008calvanese}
\@writefile{lof}{\contentsline {figure}{\numberline {4.13}{\ignorespaces Diagrammatic representation of the football leagues KB \cite  {2008calvanese}.\relax }}{87}{figure.caption.48}}
\newlabel{fig:ontFootball}{{\M@TitleReference {4.13}{Diagrammatic representation of the football leagues KB \cite  {2008calvanese}.\relax }}{87}{Diagrammatic representation of the football leagues KB \cite {2008calvanese}.\relax }{figure.caption.48}{}}
\@writefile{lot}{\contentsline {table}{\numberline {4.4}{\ignorespaces Answers to the CQ~\ref  {eqn:ontFootballQuery} over the ontology instance in Figure~\ref  {fig:ontFootballInst}.\relax }}{88}{table.caption.49}}
\newlabel{tab:ontFootballAnswer}{{\M@TitleReference {4.4}{Answers to the CQ~\ref  {eqn:ontFootballQuery} over the ontology instance in Figure~\ref  {fig:ontFootballInst}.\relax }}{88}{Answers to the CQ~\ref {eqn:ontFootballQuery} over the ontology instance in Figure~\ref {fig:ontFootballInst}.\relax }{table.caption.49}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {4.14}{\ignorespaces Diagrammatic representation of an ABox of the football leagues ontology.\relax }}{88}{figure.caption.50}}
\newlabel{fig:ontFootballInst}{{\M@TitleReference {4.14}{Diagrammatic representation of an ABox of the football leagues ontology.\relax }}{88}{Diagrammatic representation of an ABox of the football leagues ontology.\relax }{figure.caption.50}{}}
\newlabel{eqn:ontFootballQuery}{{4.48}{88}{}{equation.4.4.48}{}}
\@writefile{toc}{\contentsline {section}{\numberline {4.5}BCNF - DLNF}{88}{section.4.5}}
\newlabel{sec:dl_bcnf}{{\M@TitleReference {4.5}{BCNF - DLNF}}{88}{BCNF - DLNF}{section.4.5}{}}
\newlabel{thm:BCNFDLNF}{{\M@TitleReference {4.10}{BCNF - DLNF}}{88}{}{theorem.4.10}{}}
\newlabel{lem:IdCmapping}{{\M@TitleReference {4.8}{BCNF - DLNF}}{89}{}{lemma.4.8}{}}
\@writefile{toc}{\contentsline {section}{\numberline {4.6}Summary}{90}{section.4.6}}
\citation{2004arenas}
\citation{2008calvanese}
\@writefile{lof}{\addvspace {10pt}}
\@writefile{lot}{\addvspace {10pt}}
\@writefile{toc}{\contentsline {chapter}{\chapternumberline {5}Conclusion}{93}{chapter.5}}
\@writefile{loa}{\addvspace {10\p@ }}
\newlabel{ch:conclusion}{{\M@TitleReference {5}{Conclusion}}{93}{Conclusion}{chapter.5}{}}
\@writefile{toc}{\contentsline {section}{\numberline {5.1}Discussion}{93}{section.5.1}}
\newlabel{sec:con_disc}{{\M@TitleReference {5.1}{Discussion}}{93}{Discussion}{section.5.1}{}}
\bibstyle{abbrv}
\bibdata{../thesis}
\@writefile{toc}{\contentsline {section}{\numberline {5.2}Future Work}{94}{section.5.2}}
\newlabel{sec:con_future}{{\M@TitleReference {5.2}{Future Work}}{94}{Future Work}{section.5.2}{}}
\bibcite{1995databases}{1}
\bibcite{2008angles}{2}
\bibcite{2006arenas2}{3}
\bibcite{2006arenas}{4}
\bibcite{2012rdbmapping}{5}
\bibcite{2002arenas}{6}
\bibcite{2003arenas}{7}
\bibcite{2004arenas}{8}
\bibcite{1974armstrong}{9}
\bibcite{2009artale}{10}
\bibcite{2000GO}{11}
\bibcite{2009baader}{12}
\bibcite{2003baader}{13}
\@writefile{toc}{\contentsline {chapter}{Bibliography}{95}{section*.52}}
\bibcite{2013baeza}{14}
\citation{DBLP:conf/pods/2013}
\bibcite{2013baeza2}{15}
\citation{DBLP:conf/pods/2013}
\bibcite{2004owl}{16}
\bibcite{1979beeribernstein}{17}
\bibcite{beeri1978}{18}
\bibcite{2005berardi}{19}
\bibcite{2001semanticweb}{20}
\bibcite{1979bernstein}{21}
\bibcite{2004rdfs}{22}
\bibcite{2009calvanese}{23}
\bibcite{2006calvanese}{24}
\bibcite{2007calvanese}{25}
\bibcite{2007calvanese2}{26}
\bibcite{2008calvanese}{27}
\bibcite{2013calvanese}{28}
\bibcite{2001calvanese}{29}
\bibcite{2013calvanese2}{30}
\bibcite{1970codd}{31}
\bibcite{1971codd2}{32}
\bibcite{1971codd}{33}
\bibcite{1974codd}{34}
\bibcite{2012darwen}{35}
\bibcite{2002darwen}{36}
\bibcite{2001embley}{37}
\bibcite{1977fagin}{38}
\bibcite{1979fagin}{39}
\bibcite{1981fagin}{40}
\bibcite{2005fagin}{41}
\bibcite{2001fanlibkin}{42}
\bibcite{2002fanlibkin}{43}
\bibcite{2004rdf}{44}
\bibcite{2010foundsemweb}{45}
\bibcite{DBLP:conf/pods/2013}{46}
\bibcite{1984johnson}{47}
\bibcite{2006kharlamov}{48}
\bibcite{2005kolahi}{49}
\bibcite{1987kunii}{50}
\bibcite{1984kupervardi}{51}
\bibcite{2002lee}{52}
\bibcite{2011lenzerini}{53}
\bibcite{2003ley}{54}
\bibcite{2013libkin}{55}
\citation{DBLP:conf/pods/2013}
\bibcite{1992mannila}{56}
\bibcite{1996mok}{57}
\bibcite{2012owl2prof}{58}
\bibcite{2012owl2semantics}{59}
\bibcite{2008poggi}{60}
\bibcite{2009romero}{61}
\bibcite{2012sangiorgi}{62}
\bibcite{2012Sequeda}{63}
\bibcite{2006semanticweb}{64}
\bibcite{2012owl}{65}
\bibcite{2006xml}{66}
\bibcite{2008xml}{67}
\bibcite{2001xsd}{68}
\bibcite{1982zaniolo}{69}
\memsetcounter{lastsheet}{113}
\memsetcounter{lastpage}{99}
